package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 22.括号生成
 * <p>
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：n = 3
 * 输出：[
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * <p>
 * 回溯算法
 */
public class GenerateParenthesis {

    public static List<String> strings = new ArrayList<>();

    public static void main(String[] args) {
        GenerateParenthesis f = new GenerateParenthesis();
        List<String> s = f.generateParenthesis2(3);
        System.out.println(s);
    }

    /**
     * 方法1 暴力法
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateAll(new char[2 * n], 0, result);
        return result;
    }

    /**
     * 方法2 回溯法
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis1(int n) {
        if (n == 0) {
            return strings;
        }
        process(new StringBuffer(), 0, n * 2);
        return strings;

    }

    /**
     * 方法3 回溯法优化 推荐!!!
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis2(int n) {
        List<String> result = new ArrayList<>();
        back(new StringBuilder(), 0, 0, n, result);
        return result;
    }

    public void back(StringBuilder cur, int open, int close, int n, List<String> result) {
        // 不满足条件的不会走任何条件,空转
        if (cur.length() == n * 2) {
            result.add(cur.toString());
        }

        // 加这个条件就不用校验了
        if (open < n) {
            cur.append('(');
            back(cur, open + 1, close, n, result);
            cur.deleteCharAt(cur.length() - 1);
        }

        // 先判断哪个都行

        // 加这个条件就不用校验了
        if (open > close) {
            cur.append(')');
            back(cur, open, close + 1, n, result);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

    public void process(StringBuffer s, int index, int n) {
        if (index >= n + 1) {
            return;
        }
        if (index == n) {
            if (valid(s.toString())) {
                strings.add(s.toString());
            }
            return;
        }
        s.append("(");
        process(s, index + 1, n);
        s.deleteCharAt(s.length() - 1);

        s.append(")");
        process(s, index + 1, n);
        s.deleteCharAt(s.length() - 1);
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    // 区别于判断回文串，判断不同类型
    public boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    public boolean valid(String s) {
        Stack<Character> stack = new Stack<Character>();

        if (s.isEmpty()) {
            return true;
        }
        char[] aa = s.toCharArray();

        if ('(' != aa[0]) {
            return false;
        }

        for (int i = 0; i < aa.length; i++) {
            if (stack.isEmpty() && ')' == aa[i]) {
                return false;
            }

            if (aa[i] == '(') {
                stack.push(aa[i]);
            } else if ('(' != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}










